// 购物单_背包附加条件
// 每个主件可以有 0 个、 1 个或 2
// 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为
// 5 等：用整数 1 ~ 5 表示，第 5
// 等最重要。他还从因特网上查到了每件物品的价格（都是 10
// 元的整数倍）。他希望在不超过 N 元（可以等于 N
// 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第 j
// 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j
// 2 ，……， j k ，则所求的总和为： v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k
// ]*w[j k ] 。（其中 * 为乘号） 请你帮助王强设计一个满足要求的购物单。
// 定义状态转移数组dp[i][j]，表示前i个物品，背包重量为j的情况下能装的最大价值。
// 例如，dp[3][4]=6，表示用前3个物品装入重量为4的背包所能获得的最大价值为6，此时并不是3个物品全部装入，而是3个物品满足装入背包的条件下的最大价值。
// 状态转移方程：
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
// dp[i-1][j]表示当前物品不放入背包，dp[i-1][j-w[i]]+v[i]表示当前物品放入背包，即当前第i个物品要么放入背包，要么不放入背包。
#include <iostream>
#include <vector>
using namespace std;
int max(int m, int n) { return m > n ? m : n; }
int dp[3200];
int main() {
  int N, n, v, p, q;
  cin >> N >> n;
  N = N / 10;
  int *ZJ_Pri = new int[n + 1]();
  int *ZJ_Imp = new int[n + 1]();
  int *FJ1_Pri = new int[n + 1]();
  int *FJ1_Imp = new int[n + 1]();
  int *FJ2_Pri = new int[n + 1]();
  int *FJ2_Imp = new int[n + 1]();
  for (int i = 1; i <= n; i++) {
    cin >> v >> p >> q;
    v = v / 10;
    if (q == 0) {
      ZJ_Pri[i] = v;
      ZJ_Imp[i] = v * p;
    } else if (FJ1_Pri[q] == 0) {
      FJ1_Pri[q] = v;
      FJ1_Imp[q] = v * p;
    } else {
      FJ2_Pri[q] = v;
      FJ2_Imp[q] = v * p;
    }
  }
  for (int i = 1; i <= n; i++)  // i---前i个物品
  {
    for (int j = N; j >= 1; j--)  // j--当前的钱数
    {
      if (j >= ZJ_Pri[i]) dp[j] = max(dp[j], dp[j - ZJ_Pri[i]] + ZJ_Imp[i]);
      if (j >= ZJ_Pri[i] + FJ1_Pri[i])
        dp[j] =
            max(dp[j], dp[j - ZJ_Pri[i] - FJ1_Pri[i]] + ZJ_Imp[i] + FJ1_Imp[i]);
      if (j >= ZJ_Pri[i] + FJ2_Pri[i])
        dp[j] =
            max(dp[j], dp[j - ZJ_Pri[i] - FJ2_Pri[i]] + ZJ_Imp[i] + FJ2_Imp[i]);
      if (j >= ZJ_Pri[i] + FJ1_Pri[i] + FJ2_Pri[i])
        dp[j] = max(dp[j], dp[j - ZJ_Pri[i] - FJ1_Pri[i] - FJ2_Pri[i]] +
                               ZJ_Imp[i] + FJ1_Imp[i] + FJ2_Imp[i]);
    }
  }
  cout << dp[N] * 10 << endl;
  delete[] ZJ_Pri;
  delete[] ZJ_Imp;
  delete[] FJ1_Pri;
  delete[] FJ1_Imp;
  delete[] FJ2_Pri;
  delete[] FJ2_Imp;
  return 0;
}